/*
根据前序遍历的第一个结点可以确定出根结点；
根据根结点在中序遍历中的位置，可以确定出左子树结点和右子树结点
*/
class Solution {
public:
    unordered_map<int, int> pos;
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n=pre.size();
        //记录中序遍历的位置
        for(int i=0;i<n;i++)
        {
            pos[vin[i]]=i;
        }
        return dfs(pre,vin,0,n-1,0,n-1);
    }
    TreeNode *dfs(vector<int> pre,vector<int> vin,int pl,int pr,int vl,int vr)
    {
        if(pl>pr)
            return nullptr;
        TreeNode *root=new TreeNode(pre[pl]);
        int leftlen=pos[pre[pl]]-vl;
        root->left=dfs(pre, vin, pl+1,pl+leftlen,vl,vl+leftlen-1);
        root->right=dfs(pre,vin,pl+leftlen+1,pr,vl+leftlen+1,vr);
        return root;
    }
};